题目分析
我做这种题目,主要是按照位数变化找规律,先看一看09有多少个2,099有多少个2,0~999有多少个2。
数学
知道原理后,使用迭代实现即可。算法的**时间复杂度为$O(log(n))$,空间复杂度为$O(log(n))$**。
我们也可以节省空间复杂度,因为n位数2的个数是$n * 10^{n - 1}$,在这里为了方便说明和使用,就使用了数组进行保存。
1 | #include<iostream> |
刷题总结
对于数学问题,我们要学习小学生的做法,这类问题往往数字很大,不能使用线性,甚至更高复杂度的代码,老老实实找规律即可。